<?php
// https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
// https://mp.weixin.qq.com/s/izZ5uiWzTagagJec6Y7RvQ

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {

    /**
     * 关键思路在于我们发现翻转整棵树就是交换每个节点的左右子节点，于是我们把交换左右子节点的代码放在了前序遍历的位置。
     * @param TreeNode $root
     * @return TreeNode
     */
    function mirrorTree($root) {
        if ($root == null) {
            return $root;
        }

        // 前序遍历
        // 交换左右子树
        $tmp = $root->left;
        $root->left = $root->right;
        $root->right = $tmp;

        // 递归左右子树，让左右子节点继续翻转它们的子节点
        $this->mirrorTree($root->left);
        $this->mirrorTree($root->right);

        return $root;
    }
}